package zuo.test4_linklist;

import java.util.HashMap;

/**
 * @Author: Forx
 * @Data: 2021/6/14
 * @Desc: Algorithm - zuo.test4_linklist how to use
 * @Version: v1.0
 */

class Node{
    int val;
    Node next;
    public Node(int val){
        this.val = val;
    }
    public Node(){
        this.val = 0;
    }
}
class randomNode {
    randomNode next;
    randomNode rand;
    int val;
    public randomNode(int val){
        this.val = val;
    }
    public randomNode(){
        this.val = 0;
    }
}

public class Hash_OrderlyTable {
    /**
     * 哈希表的简单介绍
     * 1)哈希表在使用层面上可以理解为一种集合结构
     * 2)如果只有key,没有伴随数据value,可以使用HashSet结构（C+中叫UnOrderedSet)
     * 3)如果既有key,又有伴随数据value,可以使用HashMap结构（C+中叫UnOrderedMap)
     * 4)有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
     * 5)使用哈希表增（put)、删（remove)、改（put)和查（get)的操作，可以认为时间复杂度为
     * 0(1),但是常数时间比较大是基础类
     * 7)放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地
     * 址的大小
     * 有关哈希表的原理，将在提升班“与哈希函数有关的数据结构”一章中讲叙原理
     *
     *
     * 有序表的简单介绍
     * 1)有序表在使用层面上可以理解为一种集合结构
     * 2)如果只有key,没有伴随数据value,可以使用TreeSet结构（C++中叫OrderedSet)
     * 3)如果既有key,又有伴随数据value,可以使用TreeMap结构（C+中叫OrderedMap)
     * 4)有无伴随数据，是TreeSet和TreeMap维一的区别，展层的实际结构是一回会不组织
     * 5)红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现
     * 不同
     * 6)放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
     * 7)放入哈希表的东西，如果不是基础类型，必须提供比较器，内部按引用传递，内存占
     * 用是这个东西内存地址的大小
     * 8)不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度
     *
     * UnOrderedMap/Set UnSortedMap/Set C++
     * 有序表的固定操作
     * 1)void put(K key,V value):将一个（key,value)记录加入到表中，或者将key的记录
     * 更新成value。
     * 2)V get(K key):根据给定的key,查询value并返回。
     * 3)void remove(K key):移除key的记录。
     * 4)boolean containsKey(K key):询问是否有关于key的记录。
     * 5)K firstKey():返回所有键值的排序结果中，最左（最小）的那个。
     * 6)K lastKey():返回所有键值的排序结果中，最右（最大）的那个。
     * 7)K floorKey(K key):如果表中存入过key,返回key;否则返回所有键值的排序结果中，
     * key的前一个。
     * 8)K ceilingKey(Kkey):如果表中存入过key,返回key;否则返回所有键值的排序结果中，
     * key的后一个。
     * 以上所有操作时间复杂度都是0(logN),N为有序表含有的记录数
     * 有关有序表的原理，将在提升班“有序表详解”一章中讲叙原理
     * */


    public static void main(String[] args) {
        int[] buff1 = {1,2,3,4,5,6,7,8};

        Node lis1 = new Node();
        Node lis2 = new Node();
        Node cur1 = lis1;
        Node cur2 = lis2;
        for (int i = 0; i < buff1.length; i++) {
            if(i < 4){
                cur1.next = new Node(buff1[i]);
                cur2.next = new Node(buff1[i]);
            }else {
                cur1.next = new Node(buff1[i]);
                cur2.next = cur1.next;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        cur1 = lis1;
        cur2 = lis2;
        Node ans = noLoopJiaodian(cur1,cur2.next);
//        while (cur1!=null){
//            System.out.println(cur1);
//            cur1 = cur1.next;
//        }
//        while (cur2!=null){
//            System.out.println(cur2);
//            cur2 = cur2.next;
//        }

    }

    /**
     * 判断一个链表是否为回文结构
     * 【题目】给定一个单链表的头节点head,请判断该链表是否为回文结构。
     * 【例子】1->2->1,返回true;1->2->2->;1,返回true;15->6->15,返回true;
     * 1->2->3,返回false。
     * 【例子】如果链表长度为N,时间复杂度达到0(N),额外空间复杂度达到0(1)。
     *
     *用栈或者首尾指针(单链表后半部分要变成逆序)
     * */


    public static boolean isPalindrome(Node head){
        if(head == null || head.next == null){
            return true;
        }
        Node n1 = head;
        Node n2 = head;
        while (n2.next != null && n2.next.next !=null){//找中点
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 = n1.next;
        n1.next = null;
        Node n3 = null;
        while (n2!=null){//逆序
            n3 = n2.next;
            n2.next = n1;
            n1 = n2;
            n2 =n3;
        }
        n3 = n1;
        n2 = head;
        boolean res = true;
        while (n1!=null && n2!=null){//恢复
            if(n1.val != n2.val){
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }
        return res;
    }

    /**
     *复制含有随机指针节点的链表
     * 【题目】一种特殊的单链表节点类描述如下
     * class Node {
     * int value;
     * Node next;
     * Node rand;
     *  Node(int val){
     *      value=val;
     *     }
     * }
     * rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节
     * 点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点
     * head,请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
     * 【要求】1.时间复杂度0(N),额外空间复杂度0(N)
     *         2....                       O(1)
     * */



    public static randomNode copyRandomN(randomNode head){
        HashMap<randomNode,randomNode> map = new HashMap<>();
        randomNode cur = head;
        while (cur!=null){
            map.put(cur,new randomNode(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }
    public static randomNode copyRandom1(randomNode head){
        if(head==null)return null;
        randomNode cur = head;
        randomNode next = null;

        /* 1-2-3-4 --> 1-1`-2-2`-3-3`-4-4`*/
        while (cur!=null){
            next = cur.next;
            cur.next = new randomNode(cur.val);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        randomNode curCopy = null;
        //copy rand field
        while (cur!=null){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand!=null?cur.rand.next:null;
            cur = next;
        }
        randomNode res = head.next;
        cur = head;
        //split links
        while (cur!=null){
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            cur = next;
        }
        return res;
    }

    /**
     * 两个单链表相交的一系列问题
     * 【题目】给定两个可能有环也可能无环的单链表，头节点head1和head2。请实
     * 现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返
     * 回null
     * 【要求】如果两个链表长度之和为N,时间复杂度请达到0(N),额外空间复杂度
     * 请达到0(1)。
     *
     * 对于无环的:
     *  先遍历一遍求得两个链表长度假设链表1的长度是a链表2的长度是b
     *  则长的那个先走b-a步
     * 对于有环的:
     *  V1:可以先用快慢指针遍历得到环的起始点,然后做标记使其变成无环的,计算之后再把环加上
     *  V2:两个有环的有三种情况,1.两个都有环且不想交.2两个都有环且交点不在环上 2.5 两个都有环且交点在环上. 3.只有一个有环
     *      分析可知3这种情况不存在交点
     *      2.这种情况可以以交点为终止点,头结点到交点前使用无环算法
     *      2.5.list1到达交点后继续走看能否遇见交点2,如果有交点则一圈之内必然能碰见list2的环起始点,否则就是情况1
     * */

    /**
     * 当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步，则fast走了2s步，又由于
     *
     * fast走过的步数 = s + n*r（s + 在环上多走的n圈），则有下面的等式：
     *
     * 2*s = s + n  * r ; (1)
     *
     *  => s = n*r (2)
     *
     * 如果假设整个链表的长度是L，入口和相遇点的距离是x，起点到入口点的距离是a，则有：
     *
     * a + x = s = n * r; (3)  由（2）推出
     *
     * a + x = (n - 1) * r + r  = (n - 1) * r + (L - a) (4) 由环的长度 = 链表总长度 - 起点到入口点的距离求出
     *
     * a = (n - 1) * r + (L -a -x) (5)
     *
     *
     * */
    public static Node getRingNode(Node node){
        if(node==null || node.next==null)return null;
        Node fast = node;
        Node slow = node;
        boolean flag = true;
        while (fast.next!=null && fast.next.next!=null && (flag || fast!=slow)){
            if(flag)flag = false;
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast.next==null || fast.next.next==null)return null;
        fast = node;
        while (fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    public static Node noLoopJiaodian(Node head1,Node head2){
        if(head1==null || head2 == null)return null;
        int len1 = 0,len2 = 0;
        Node cur = head1;
        while (cur!=null){
            len1++;
            cur = cur.next;
        }
        cur = head2;
        while (cur!=null){
            len2++;
            cur = cur.next;
        }
        int diff = Math.abs(len1 - len2);
        Node bigger = len1>len2?head1:head2;
        Node smaller = len1>len2?head2:head1;
        while (diff!=0){
            bigger = bigger.next;
            diff--;
        }
        while (bigger!=null&&bigger!=smaller){
            bigger = bigger.next;
            smaller = smaller.next;
        }
        return bigger;
    }
    public static Node unSureLoopJiaodian(Node head1,Node head2,Node end1,Node end2){
        if(head1==null || head2 == null)return null;

        if(end1==end2){
            int len1 = 0,len2 = 0;
            Node cur = head1;
            while (cur!=end1){
                len1++;
                cur = cur.next;
            }
            cur = head2;
            while (cur!=end2){
                len2++;
                cur = cur.next;
            }
            int diff = Math.abs(len1 - len2);
            Node bigger = len1>len2?head1:head2;
            Node smaller = len1>len2?head2:head1;
            while (diff!=0){
                bigger = bigger.next;
                diff--;
            }
            while (bigger!=end1&&bigger!=smaller){
                bigger = bigger.next;
                smaller = smaller.next;
            }
            return bigger;
        }else {
            Node cur = end1;
            while (cur!=null){
                cur = cur.next;
                if(cur==end2)return cur;
            }
            return null;
        }
    }
    public static Node getJiaodian(Node head1,Node head2){
        if(head1==null || head2 == null)return null;
        Node loop1 = getRingNode(head1);
        Node loop2 = getRingNode(head2);
        Node cur1 = null;
        Node cur2 = null;
        if(loop1==null && loop2==null){
            return noLoopJiaodian(head1,head2);
        }else{
            if(loop1==null || loop2==null)return null;//只有一个有环的情况
            return unSureLoopJiaodian(head1,head2,loop1,loop2);
        }
    }
}
